class Solution {
public:
    string longestPalindrome(string s) {
        // 使用动态规划解决，dp[i][j]代表i到j范围内的字符串是否能够构成最长回文子串，这样j-i+1就是这个字符串的长度
        // i就是这个字符串的起始位置，现在去分析状态转移方程
        // 如果arr[i] == arr[j]那么dp[i][j] =
        // dp[i+1][j-1],如果arr[i]!=arr[j]那么dp[i][j] = false 不需要进行计算
        int n = s.size();
        int start = 0;
        int max_size = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        // 现在开始填表，因为在填ij的时候需要使用到i+1,j-1所以填表顺序就是从下往上，从左往右
        string ret;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = i + 1 < j-1 ? dp[i + 1][j - 1] : true;
                }//计算i到j范围内的字符串是否为回文子串
                if(dp[i][j])
                {
                    //记录最长的回文子串
                    if(j-i+1>max_size)
                    {
                        max_size = j-i+1;
                        start = i;
                    }
                }
            }
        }
        return s.substr(start,max_size);
    }
};